High dependability and reliability is a goal of all computer and software systems. Complex systems, such as knowledge-based systems and expert systems, in general cannot attain high dependability without addressing crucial remaining open issues of software dependability. The need for ultrahigh dependable systems increases continually, along with a corresponding increasing need to ensure correctness in system development. Correctness exists where the implemented system is equivalent to the requirements, and where this equivalence can be mathematically proven.
Knowledge-based systems and expert systems are examples of a general class of inferencing systems that comprise an inference engine and separate knowledge and rule bases. The inference engine itself does not include domain knowledge, but the knowledge and rule bases are specific to the domain and are used by the inference engine, and the combination of these elements implements a knowledge-based system application. Further, during the operation of a particular knowledge-based system (i.e., application), the firing of rules by the inference engine may dynamically modify the knowledge base (which contains the essential application facts or data), and the resulting changes determine the subsequent course of execution of the running application. It is possible, though not typical, that the running application will modify its own rule base, and some such systems could be classified as “learning” systems.
Knowledge-based systems, expert systems and inferencing systems in general are each referred to as a KBS herein.
The development of a KBS begins with the development of a requirements specification, such as a formal specification or an informal specification that represents domain knowledge. A formal specification might be encoded in a high-level language such as Prolog, whereas domain knowledge in the form of an informal specification can be expressed in restricted natural language, “if-then” rules, graphical notations, English language, programming language representations, flowcharts, scenarios or even using semi-formal notations such as unified modeling language (UML) use cases.
A scenario may be defined as a natural language text (or a combination of any, e.g. graphical, representations of sequential steps or events) that describes the software's actions in response to incoming data and the internal goals of the software. Some scenarios may also describe communication protocols between systems and between the components within the systems. Also, some scenarios may be known as UML use-cases. Preferably, a scenario describes one or more potential executions of a system, describing what happens in a particular situation, and what range of behaviors is expected from or omitted by the system under various conditions.
Natural language scenarios are usually constructed in terms of individual scenarios written in a structured natural language. Different scenarios may be written by different stakeholders of the system, corresponding to the different views they have of how the system will perform, including alternative views corresponding to higher or lower levels of abstraction. Natural language scenarios may be generated by a user with or without mechanical or computer aid. The set of natural language scenarios provides the descriptions of actions that occur as the software executes. Some of these actions will be explicit and required, while others may be due to errors arising, or as a result of adapting to changing conditions as the system executes.
For example, if the system involves commanding space satellites, scenarios for that system may include sending commands to the satellites and processing data received in response to the commands. Natural language scenarios might be specific to the technology or application domain to which they are applied. A fully automated general purpose approach covering all domains is technically prohibitive to implement in a way that is both complete and consistent. To ensure consistency, the domain of application might be specific-purpose. For example, scenarios for satellite systems may not be applicable as scenarios for systems that manufacture agricultural chemicals.
After completion of an informal specification that represents domain knowledge, the KBS is developed. A formal specification is not necessarily used in the development of a KBS.
In the development of some KBS's, computer readable code is generated. The generated code is encoded in a computer language, such as a high-level computer language. Examples of the languages include Java Expert System Shell (JESS®), C Language Integrated Production System (CLIPS) and Prolog. One example of such a KBS is the Reduced Operations by Optimizing Tasks and Technology (ROBOTT) system. ROBOTT is a system which performs performance and safety monitoring on the POLAR and X-Ray Timing Explorer (XTE) satellites. ROBOTT is a KBS with rules expressed in CLIPS.
One step in creating a KBS with high dependability and reliability is verification and validation that the executable KBS accurately reflects the requirements. Validation of the generated code is sometimes performed through the use of a domain simulator, a very elaborate and costly approach that is computationally intensive. This process of validation rarely results in an unambiguous result and rarely results in uncontested results among systems analysts. In some examples, a KBS is validated through parallel mode, shadow mode operations with a human operated system. This approach can be very expensive and exhibit severely limited effectiveness. In some complex systems, this approach leaves vast parts of possible execution paths forever unexplored and unverified.
During the life cycle of a system, requirements typically evolve. Manual change to the system creates a risk of introducing new errors and necessitates retesting and revalidation, which can greatly increase the cost of the system. Often, needed changes are not made due to the cost of verifying/validating consequential changes in the rest of the system. Sometimes, changes are simply made in the code and not reflected in the specification or design, due to the cost or due to the fact that those who generated the original specification or design are no longer available.
For the reasons stated above, and for other reasons stated below which will become apparent to those skilled in the art upon reading and understanding the present specification, there is a need in the art for an automated, generally applicable way to verify that an implemented system is a provably correct implementation of domain knowledge. There is also a need for a process for requirements validation that does not require large computational facilities.